Field of the Invention
The present application relates to databases and methods for storing and searching data in database tree structures. In particular, but not exclusively, the present application relates to the processing of data stored in database tree structures for use in data packet routing applications.
Description of the Related Technology
Internet protocol (IP) networks include a number of interconnected router entities which are responsible for making decisions as to which paths data packets may flow through from source to destination. Routing protocols are used to gain information about the network and to determine routes between particular network destinations or different areas or subnets of the network. These routes may be stored at each router in a database known as a routing table. The process of creating and maintaining the contents of a routing table is commonly referred to as IP routing.
A router may also store information necessary for carrying out forwarding of data packets in a database commonly known as a forwarding table. The process of receiving and transmitting data packets onto their destination using information stored in a forwarding table is commonly referred to as IP forwarding.
A routing table is generally not used directly in the packet forwarding process. Instead, the packet routing process outputs data relating to selected routes to a forwarding table according to route information and one or more routing protocols such as the Routing Information Protocol (RIP) or the Border Gateway Protocol (BGP). The contents of the forwarding table may then be accessed during the packet forwarding process, for example using efficient hardware implementations.
A data packet transmitted into an IP network will include an IP destination address. IPv4 addresses are 32 bits long, which gives scope for over 4 billion IP addresses, and IPv6 addresses are still larger. Exchanging and updating forwarding information for this number of IP addresses at each router is generally impractical.
Instead, a router will typically maintain a forwarding table containing a number of IP address prefix entries and forwarding information corresponding to each of these prefix entries. When information relating to a network destination address arrives at a router, an IP address for the network destination may be examined by the router which may then search its routing table for the longest match to the IP destination address for the network destination. The longest match comes in the form of the longest prefix matching the destination IP address, i.e. the route which has the greatest number of initial bits matching the IP network address. This is known as the ‘longest prefix match.’
The router may then output this information to a forwarding table, so that when data packets for this destination address arrive at the router, they may be forwarded by a packet forwarding function or module in the router using forwarding information contained in the forwarding table. The packet forwarding process may be repeated as often as required, and a data packet may be forwarded from router to router, until it arrives at the desired IP destination address.
An IPv4 address is typically denoted as a series of four decimal numbers separated by decimal points. Each of the decimal numbers represents eight bits of a 32 bit IPv4 address, so that each decimal number ranges from zero to 255.
A prefix refers to an IP address or its initial portion. Using IPv4 for example “192.168/16” is a 16-bit prefix of “192.168.1.4”, “192.168.200.200” and “192.168.26.8”, etc. In fact, “192.168/16” is a 16-bit prefix of all the addresses “192.168.x.y” where 0≦x≦255 and 0≦y≦255. A routing table at a router containing routing information for the prefix “192.168/16” may thus be able to route data packets for all IP destination addresses in the range “192.168.x.y”. However, the router may also contain more specific routing information for a 32 bit IP destination such as “192.168.4.5”. A network IP address may thus be compared with all prefixes in the router's routing table in order to provide suitable, e.g. the most specific, routing information in the form of the longest matching prefix, which may then be output to a forwarding table.
Routing in IP networks thus involves a large amount of searching through routing tables of a large number of routers. Further, the routing tables may change frequently when new routes are added and other routes become obsolete. It is therefore desirable that the algorithms and data structures for implementing such systems are efficient in terms of high search speed whilst required data storage resources are kept down.
A tree is a widely-used data structure with a tree-shaped form having a set of linked nodes stemming from a root node. Each node may contain a value or a condition and has zero or more child nodes, which are located immediately below it in the tree. A node that has a child is called the child's parent. A node has at most one parent. A leaf node is a node of a tree data structure that has zero child nodes, which are often furthest from the root node.
An ancestor of a node is that node's parent, or that node's parent's parent, and so on. The root is ancestor to every other node in the tree. The set of ancestors of a given node are the (shortest) path through the tree from the root to that node. The descendants of a node are that node's children, or that node's children's children, and so on. Node A is an ancestor of node B if and only if node B is a descendant of node A.
A binary search tree is a binary tree data structure where each node has a corresponding key. The left subtree of a node in a binary search tree contains only values less than the node's value and the right subtree of a node in a binary search tree contains only values greater than or equal to the node's value. Sorting and search algorithms for binary trees tend to be relatively efficient.
A digital tree is a tree for storing strings in which nodes are organised by substrings common to two or more strings. Searching of a digital tree involves use of the search keys only, i.e. values associated with each node are not read at each node as the tree is traversed. Instead, a node value may be read only once a suitable node key is found during search of the tree.
A trie, sometimes called a prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are strings. Unlike a binary search tree, no node in the tree stores the key associated with that node. Instead, the position of a node in the tree determines what key the node is associated with. All the descendants of any one node have a common prefix of the string associated with that node. The root node is commonly associated with the empty string.
Advantages of tries include fast key lookup time and their suitability for longest-prefix matching. Longest-prefix matching involves identifying a node whose node key shares the longest prefix with a given search key. Tries also allow association of a search key with an entire group of node keys that have a common prefix. Tries have a disadvantage that when the set of node keys is sparse, i.e. when the actual node keys form a small subset of the set of potential keys, many of the internal nodes (non-leaf nodes) in the trie only have one descendant, giving the trie a high space occupancy.
The Patricia algorithm, ‘Practical Algorithm to Retrieve Information Coded in Alphanumeric’, (Donald R. Morrison, Journal of the ACM, Column 15, Issue 4, October 1968, pp 514-534) is an algorithm which provides a flexible means of storing, indexing, and retrieving information in a large file, which is economical of index space and of re-indexing time. It does not require rearrangement of text or indices as new material is added. The Patricia algorithm can be used to create and process Patricia tree structures.
A Patricia tree, sometimes called a radix tree, is an example of a binary digital trie in which any node which is an only child is merged with its parent. Traversal of a conventional trie uses every part of the key to determine which subtree to branch to, whereas by storing a search key part identifier, a Patricia tree nominates which element of the search key should be used next to determine the branching and hence which node should be traversed next. This removes the need for any nodes in the tree with just one descendant, so that only genuine branches are included in the index. This means that the index size is independent of the length of stored phrases.
The Patricia algorithm allows quick determination of whether a search key corresponds to a node key in the tree, for n nodes requiring ‘of the order of log n’ computations (O(log n)), whether a search key is prefixed by any node key in the tree, and if so which such prefix is longest in O(log n) computations, and whether a search key prefixes any node keys in the tree in O(log n) computations, and if so to walk through the m node keys prefixed in O(m) computations. These properties make the Patricia algorithm a suitable choice for IP forwarding applications which rely on fast matching of IP destination addresses to prefixes, i.e. search keys to node keys.
A data structure constructed according to the Patricia algorithm has a limitation in that node keys stored in the data structure cannot prefix one another.
Various attempts have been made to tackle this limitation, for example United States patent U.S. Pat. No. 6,396,842 B1 describes a method of searching utilising a longest match based radix search trie with variable length keys and having the ability to handle keys which are prefixes of other keys. The method is based on the Patricia algorithm. The address prefixes representing the keys for the tree are modified before being processed by the algorithm. A single byte is added to the beginning of each address prefix which is set equal to the length of the address prefix. The combined address length byte followed by the address prefix is used by the Patricia algorithm. When one address is the prefix of another, the added byte will make both addresses unique and distinct from each other. A Patricia algorithm can be used to search the trie since the node keys have been made unique. In tackling the key prefix limitation of Patricia, performance is degraded as this method requires increased memory capacity and also requires additional searches for different prefix lengths.
Other attempts to tackle the key prefix limitation of tree data structures, such as those constructed according to the Patricia algorithm, destroy desirable properties of the tree data structures, for example requiring frequent inspection of node keys as the tree is traversed.
It would therefore be desirable to provide an improved solution to overcome the node key prefix limitation of algorithms for processing data in tree data structures similar to the Patricia algorithm.